// https://leetcode-cn.com/problems/3sum/
// 15. 三数之和
// 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c，
// 使得 a + b + c = 0 ? 请你找出所有和为 0 且不重复的三元组
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];

    // sort ascending
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        const a = nums[i];

        if (a > 0) return result;
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }

        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            if (a + nums[left] + nums[right] < 0) {
                left++;
            } else if (a + nums[left] + nums[right] > 0) {
                right--;
            } else {
                result.push([a, nums[left], nums[right]]);

                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;

                left++;
                right--;
            }
        }
    }

    return result;
}
